Advanced computer graphics technologies have been applied to a wide variety of practical fields such as industrial design, aerospace, consumer electronics, telecommunications, entertainment, and medicine, to name but a few. Important and basic functions of most types of computer-implemented graphics applications are the modeling and visualization of, and the interaction with, represented real-world or imaginary objects. These functions require robust and computationally efficient processes for manipulating the data structures that represent the objects.
For example, numerous medical interventions involve placing a needle, drill, surgical instrument, or other device in the body. In some cases the angle and position of the device with respect to specific body structures is of critical importance, for example in the drilling of a hole for a screw along the axis of a spinal pedicle. In other cases, it is primarily the relative positioning of the instrument in organs which is important, for example, placing a catherization tool in the heart or arteries.
In all of these applications, computer graphics are extensively used, and many of these problems can be modeled in two dimensions (2D) as arrangements of line segments in a plane. The line segments are visualized as pixels on a display device. For example, the outline of the heart chambers and major arteries can be represented as poly-lines, i.e., connected sets of many small line segments. In another example, geographical features contained in maps in geographical information systems may be represented as line segments in a plane.
Fundamental to the functions of interacting with, and the visual display of objects modeled as arrangements of line segments, is the problem of finding and correctly identifying their relative position, for example, do the lines intersect. The line segment intersection problem is also one of the fundamental problems of computational geometry that has received considerable attention.
In a typical prior art formulation of the problem, two line segments are given, and the task is to identify whether the lines intersect each other. Depending on the specification of the problem, two line segments can be considered intersecting when the two lines share a single coordinate point P(x, y) in Euclidean space. Visually this is easy to discern, but computationally this is a relatively difficult task.
For a first line segment defined by end points (x1,y1) and (x2,y2), and a second line segment (x3,y3) and (x4,y4), the common method used to determine if the two line segments intersect includes three major steps.
First, intersect the two line segments as if they were infinite lines using the formulation: EQU x=(b1*c2-b2*c2)/(a1*b2-a2*b1),
and EQU y=(c1*a2-c2*a1)/(a1*b2-a2*b1),
where EQU a1=y2-y1, a2=y4-y3, b1=x1-x2, b2=x3-x4, EQU c1=(x2 * y2)-(x1 * y2), c2=(x4 * y3)-(x3-y4).
Second, check whether the intersection point P(x, y) belongs to the first line segment: EQU x1&lt;=x&lt;=x4, y1&lt;=y&lt;=y4 or (if x2&lt;x1 or y2&lt;y1) EQU x2&lt;=x&lt;=x1, y2&lt;=y&lt;=y1.
Third, check whether the intersection point P(x, y) belongs to the second line segment: EQU x3&lt;=x&lt;=x4, y3&lt;=y&lt;=y4 or (if x4&lt;x3 or y4&lt;y3) EQU x4&lt;=x&lt;=x3, y4&lt;=y&lt;=y3.
If both conations are true, then coordinate P(x, y) is shared by both line segments, and is their intersection point.
Obviously, this method requires a large number of arithmetic and logical computational steps to determine P(x, y), particularly multiple divisions. This is true even in the case where the lines do not intersect. In addition, the computations need to be performed with real numbers that require substantial computer resources, such as floating-point logic units. The computational costs increase when there are a large number of line segments to be checked. If a significant number of line segments do not intersect, then time and resources are wasted.
It is possible to filter out some non-intersecting line segments using a method described by Berg et al. in "Computational Geometry: Algorithms and Applications," Springer-Verlag, pp.21-22, 1997. In that method, the pair of line segments is projected onto the X and Y axes. If their projection does not overlap, then the lines cannot intersect. However, this is only a necessary, and not a sufficient condition. Projected line segments can overlap without intersecting.
Chazelle et al. in "An optimal algorithm for intersecting line segments in the plane," Journal of the ACM, v. 39 , pp. 1-54, 1992 describe how to identify the intersection of many line segments. Their goal could be formulated as follows. Given a set S of n line segments in a plane, report all intersection points among the line segments S. Their major concern is to organize a search among analyzed segments, and not to miss any intersections without having to intersect every pair of line segments, or to intersect segments more than once.
It is desired to provide a method for determining the intersection of two line segments that represent both necessary and sufficient conditions. In addition, it is desired that this method can be performed without using floating-point computational resources in a minimal number of computational steps. Furthermore, it is desired to determine, in a more general sense, not only intersection, but other relative positions of line segments with respect to each other.